package day28_35.day29;

public class Solution {
    /**
     *	正数数组中的最小不可组成和
     *	输入：正数数组arr
     *	返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        //第一个循环获取到最大和最小值
        for (int i = 0 ; i < arr.length ; i ++){
            min = Math.min(arr[i] , min);
            max += arr[i];
        }
        //boolean数组确定最小到最大的所有数字位
        boolean[] arrTrue = new boolean[max + 1];
        arrTrue[0] = true;

        for (int i = 0 ; i < arr.length ; i++){
            //循环每个数字
            for (int j = max ; j >= arr[i] ; j--){
                //从最大值开始依次到当前值判断是否能够通过相加组合得到,妙在这里，持续遍历原数组后，每个真值都可以通过组合获得
                arrTrue[j] = arrTrue[j - arr[i]] || arrTrue[j];
            }
        }
        for (int i = min ; i < max ; i++){
            if (!arrTrue[i]){
                return i;
            }
        }
        return max + 1;
    }
}